package algorithm.leetcode;

/**
 * 正则表达式匹配.*
 *
 */
public class Regular {

    public boolean match(String s, String p) {
        return doMatch(0,0,s, p);
    }

    public boolean doMatch(int i, int j, String s, String p) {
        if(i >= s.length()) {
            return j >= p.length()-1;
        }
        if(j >= p.length()){
            return false;
        }
        //如果相同，看下一个字符是否相同
        if(s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
            return doMatch(i+1, j+1, s, p);
        }

        if(p.charAt(j) == '*') {
            return doMatch(i, j-1, s, p);
        }

        if(p.charAt(j+1) == '*') {
            return doMatch(i, j+2, s, p);
        }
        return false;
    }

    public static void main(String[] args) {
//        System.out.println(new Dynamic().match("aab", "c*a*b"));

        System.out.println(new Regular().match("mississippi", "mis*is*p*"));
    }
}